/////////////////////////////////////////////////////////////////////////////
//
//  Alexey ActionScript Library
//  Kolonitsky Developers Alliance (c) 2012
//  All rights received
//
/////////////////////////////////////////////////////////////////////////////

package org.kolonitsky.alexey.algorithm
{

    /**
     * Breadth-first search alghorithm. 
     * 
     * This class work with vector of node's ID instead of matrix. 
     * Developer must decide how to acess node neighbour by current node ID. 
     * This abstract layer from data structures and give more freedom to 
     * developers. Function for retrieving neighgours passed to each method.
     * 
     * Full alhorigthm devided on to steps.
     * <ol>
     *   <li><b>Calculate distancies</b> from start node to finish. This step can 
     *     calculate distancies to all graph if it not dynamicly changed.</li>
     *   <li><b>Find path</b> from start node to finish node useing calculated 
     *      distancies.</li>
     * </ol>
     * 
     * For save performance and make algorithm more flexible this steps 
     * divided to separed functions. Your can calculate all work matrix
     * and build path from any point to any other.
     * 
     * @author Alexey Kolonitsky
     */
    public class BreadthFirst
    {
        /**
         * Create vector with distances from startIndex (start node id)
         * to endIndex (end node id). This method put startIndex to q and
         * invoke getNeigmburs method for it. Method stop calculation when
         * find neighbour with index == endIndex. If endIndex == start index
         * method calculate distancies to all nodes.
         *
         * @param source source object which passed to getNighbours function
         * @param startIndex index of start node
         * @param endIndex index of finish node
         * @param getNeighburs is a function that retrive indexes of neighbors.
         * Function must have following signature:
         * <pre>
         * getNigbour(source:Object, index:uint):Vector.&lt;uint&gt;
         * </pre>
         *
         * @return vector of distances by identifiers.
         */
        public static function bfs(source:Object,
            startIndex:uint, endIndex:uint,
            getNeighburs:Function):Vector.<uint>
        {
            var i:int, N:uint = source.length;
            var q:Vector.<uint> = new Vector.<uint>();
            q.push(startIndex);

            var distance:Vector.<uint> = new Vector.<uint>(N);
            for (i = 0; i < N; i++)
                distance[i] = uint.MAX_VALUE;
            distance[startIndex] = 1;

            while (q.length)
            {
                var curIndex:uint = q.shift();
                if (curIndex == endIndex && curIndex != startIndex)
                    break;

                var neighbors:Vector.<uint> = getNeighburs(source, curIndex);
                for (i = 0; i < neighbors.length; i++)
                {
                    var neighborIndex:uint = neighbors[i];
                    if (q.indexOf(neighborIndex) == -1
                        && distance[neighborIndex] > distance[curIndex] + 1)
                    {
                        distance[neighborIndex] = distance[curIndex] + 1;
                        q.push(neighborIndex);
                    }
                }
            }

            return distance;
        }

        /**
         * Create vector with distances from startIndex (start node id)
         * to endIndex (end node id). This method put startIndex to q and
         * invoke getNeigmburs method for it. Method stop calculation when
         * find neighbour with index == endIndex. If endIndex == start index
         * method calculate distancies to all nodes.
         *
         * @param source source object which passed to getNighbours function
         * @param startIndexes index of start node
         * @param getNeighburs is a function that retrive indexes of neighbors.
         * Function must have following signature:
         * <pre>
         * getNigbour(source:Object, index:uint):Vector.&lt;uint&gt;
         * </pre>
         *
         * @return vector of distances by identifiers.
         */
        public static function bfsArray(source:Object,
            startIndexes:Vector.<uint>,
            getNeighburs:Function):Vector.<uint>
        {
            var i:int = 0, N:uint = source.length;
            var q:Vector.<uint> = startIndexes;

            var distance:Vector.<uint> = new Vector.<uint>(N);
            for (i = 0; i < N; i++)
                distance[i] = uint.MAX_VALUE;

            for (i = 0; i < q.length; i++)
                distance[q[i]] = 1;

            while (q.length)
            {
                var curIndex:uint = q.shift();
                var neighbors:Vector.<uint> = getNeighburs(source, curIndex);
                for (i = 0; i < neighbors.length; i++)
                {
                    var neighborIndex:uint = neighbors[i];
                    if (q.indexOf(neighborIndex) == -1
                        && distance[neighborIndex] > distance[curIndex] + 1)
                    {
                        distance[neighborIndex] = distance[curIndex] + 1;
                        q.push(neighborIndex);
                    }
                }
            }

            return distance;
        }

        /**
         * Find path in source graph useing <code>bfs()</code> calculation
         * result. 
         * 
         * This method have the similiar signature except distances paramter.
         *
         * @param source graph in which path has founded
         * @param distance vector of distancies calculated with <cod>bfs()</code> function
         * @param startIndex index of start node
         * @param endIndex index of finish node
         * @param getNeighbors is a function that retrive indexes of neighbors.
         * Function must have following signature:
         * <pre>
         * getNigbour(source:Object, index:uint):Vector.&lt;uint&gt;
         * </pre>
         *
         * @return vector of vertex indexes in optimal path from node with startIndex 
         * to node with endIndex.
         */
        public static function bfsPath(source:Object, distance:Vector.<uint>,
            startIndex:uint, endIndex:uint,
            getNeighbors:Function):Vector.<uint>
        {
            var cur:int = endIndex, i:int, j:int, N:int = distance[endIndex];
            var neighbours:Vector.<uint> = new Vector.<uint>();
            var neighboursCount:int = 0;
            var result:Vector.<uint> = new Vector.<uint>(N);
            result[N - 1] = endIndex;

            for (i = N - 2; i > 0; i--)
            {
                neighbours = getNeighbors(source, cur);
                neighboursCount = neighbours.length;

                j = 0;
                while (j < neighboursCount && distance[neighbours[j]] != i + 1)
                    j++;

                cur = result[i] = neighbours[j];
            }

            result[0] = startIndex;
            return result;
        }

    }
}
